package com.fml.leecode.eaysy;

/**
 * 67. 二进制求和
 * 简单
 * 给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。
 *
 * 示例 1：
 *
 * 输入:a = "11", b = "1"
 * 输出："100"
 * 示例 2：
 *
 * 输入：a = "1010", b = "1011"
 * 输出："10101"
 *
 *
 * 提示：
 *
 * 1 <= a.length, b.length <= 104
 * a 和 b 仅由字符 '0' 或 '1' 组成
 * 字符串如果不是 "0" ，就不含前导零
 */
public class Demo67 {
    public static String addBinary(String a, String b) {

        //倒位相加，字符串反转
        //从低位开始相加，依次向前
        int sum = 0;
        StringBuilder sb = new StringBuilder();
        //sum!=0 是为了防止最高位进位
        for (int i = a.length() - 1, j = b.length() - 1; i >= 0 || j >= 0 || sum != 0; i--, j--) {
            //a.charAt(i) - '0' 是为了防止字符编码转换为ASCII编码
            //比如 '1' 转换为ASCII编码为49，'0' 转换为ASCII编码为48
            sum += i >= 0 ? a.charAt(i) - '0' : 0;
            sum += j >= 0 ? b.charAt(j) - '0' : 0;
            //求余数算下一位
            sb.append(sum % 2);
            //求商，为下一位相加做准备
            sum /= 2;
        }
        //遍历相加完成，字符串反转
        return sb.reverse().toString();
    }


    public static void main(String[] args) {
//        System.out.println(addBinary("11", "1"));
        System.out.println("========");
        System.out.println(addBinary("1010", "1011"));
        System.out.println("=========");
//        System.out.println(add1("1010", "1010"));

    }


    /**
     * 求和
     * @param a
     * @param b
     * @return
     */
    private static String add2(String a, String b) {
        StringBuilder sb = new StringBuilder();

        int i = a.length() - 1;
        int j = b.length() - 1;
        int carry = 0;
        while (i >= 0 || j >= 0) {
            int sum = carry;
            if (i >= 0) {
                sum += a.charAt(i--) - '0';
            }
            if (j >= 0) {
                sum += b.charAt(j--) - '0';
            }
            sb.append(sum % 2);
            carry = sum / 2;
        }
        if (carry != 0) {
            sb.append(carry);
        }
        return sb.reverse().toString();
    }

}
